package bTree.LeetCode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class 下一个更大元素1 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int[] res = new int[len1];
        int[] res2 = new int[len2];
        //用哈希表隐射nums2的索引和值，同时进行单调栈存储结果
        Map<Integer, Integer> map = new HashMap<>();
        map.put(nums2[0], 0);
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < len2; i++) {
            map.put(nums2[i], i);
            if (nums2[i] <= nums2[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.empty() && nums2[i] > nums2[stack.peek()]) {
                    res2[stack.pop()] = nums2[i];
                }
                stack.push(i);
            }
        }
        for (int i = 0; i < len1; i++) {
            Integer i1 = map.get(nums1[i]);
            int i2 = res2[i1];
            if (i2 == 0) {
                res[i] = -1;
            } else {
                res[i] = i2;
            }


        }
        return res;
    }
}